//给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c +
// d 的值与 target 相等？找出所有满足条件且不重复的四元组。 
//
// 注意：答案中不可以包含重复的四元组。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,0,-1,0,-2,2], target = 0
//输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
// 
//
// 示例 2： 
//
// 
//输入：nums = [], target = 0
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 200 
// -109 <= nums[i] <= 109 
// -109 <= target <= 109 
// 
// Related Topics 数组 双指针 排序 
// 👍 909 👎 0


package service.exercise.medium.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//Java：四数之和
public class P18FourSum {
    public static void main(String[] args) {
        Solution solution = new P18FourSum().new Solution();
        // TO TEST
        System.out.println(solution.fourSum(new int[]{2, 2, 2, 2, 2}, 8));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            //先排序
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                //去重
                System.out.println(i);
                System.out.println(i > 1 && nums[i] == nums[i - 1]);
                if (i >= 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                List<List<Integer>> lists = threeSum(nums, i + 1, target - nums[i]);
                for (List<Integer> temp:lists){
                    temp.add(nums[i]);
                    res.add(temp);
                }
            }
            return res;

        }

        //先写两数之和
        private List<List<Integer>> twoSum(int[] nums, int start, int target) {
            List<List<Integer>> res = new ArrayList<>();
            int len = nums.length - 1;
            for (int i = start; i < nums.length; i++) {
                //去重
                if (i > start && nums[i] == nums[i - 1]) {
                    continue;
                }
                while (i < len && nums[i] + nums[len] > target) {
                    len--;
                }
                if (i < len && nums[i] + nums[len] == target) {
                    res.add(new ArrayList<>(Arrays.asList(nums[i], nums[len])));
                }
            }
            return res;
        }

        //写三数之和
        private List<List<Integer>> threeSum(int[] nums, int start, int target) {
            List<List<Integer>> res = new ArrayList<>();
            for (int i = start; i < nums.length; i++) {
                if (i > start && nums[i] == nums[i - 1]) {
                    continue;
                }
                List<List<Integer>> lists = twoSum(nums, i+1, target-nums[i]);
                for (List<Integer> temp : lists) {
                    temp.add(nums[i]);
                    res.add(temp);
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}